#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        vector<int> dp(s.size(), -1); // 1:true,0:false,-1:unchecked
        return CheckBreak(s, wordDict, dp, 0);
    }

    bool CheckBreak(const string &s, vector<string> &wordDict, vector<int> &dp, int start)
    {
        if (start == s.size())
            return true;
        if (dp[start] != -1)
            return dp[start];
        for (string &word : wordDict)
        {
            if (start + word.size() <= s.size() && s.substr(start, word.size()) == word)
            {
                if (CheckBreak(s, wordDict, dp, start + word.size()))
                {
                    dp[start] = true;
                    break;
                }
            }
        }
        if (dp[start] == -1)
            dp[start] = false;
        return dp[start];
    }
};

int main()
{
    cout << "Code139" << endl;
    Solution s;
    string ss = "applepenapple";
    vector<string> wordDict = {"apple", "pen"};
    cout << boolalpha << s.wordBreak(ss, wordDict) << endl;
    return 0;
}